package com.learn.algorlthm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @classname:
 * @Description:把二叉树打印成多行
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-01 14:15
 *
 * 题目描述：
 * 和 Learn32_1 几科一样
 */
public class Learn32_2 {


    public static void printTree() {
        TreeNode treeNode = getTreeNode();

        List<TreeNode> list = new ArrayList<>();
        list.add(treeNode);

        int length = list.size();
        for (int i = 0; i < length; i++) {
            TreeNode root = list.get(i);
            if (root.left != null)
                list.add(root.left);

            if (root.right != null)
                list.add(root.right);

            if (root.left != null || root.right != null)
                length++;

        }

        for (int i = 0, index = 1; i < list.size(); i++) {
            System.out.print(list.get(i).value);

            if ((i + 1) == (Math.pow(2, index) - 1)) {
                System.out.print("\n");
                index++;
            } else {
                System.out.print(" ,");
            }

        }

    }



    public static TreeNode getTreeNode() {
        int[] values = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 ,18, 19, 20};
//        int[] values = {1 ,2, 3, 4, 5, 6, 7};

        LinkedList<TreeNode> list = new LinkedList<>();
        for (int value : values) {
            list.add(new TreeNode(value));
        }

        for (int preIndex = 0; preIndex < values.length/2 -1; preIndex++) {

            TreeNode node = list.get(preIndex);
            node.left = list.get(preIndex *2 + 1);
            node.right = list.get(preIndex * 2 + 2);
        }

        int lastIndex = values.length/2 - 1;
        list.get(lastIndex).left = list.get(lastIndex * 2 +1);
        if (values.length % 2 != 0)
            list.get(lastIndex).right = list.get(lastIndex * 2 +2);


        return list.get(0);
    }

    static class TreeNode{
        public Integer value;

        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(Integer value) {
            this.value = value;
        }
    }

}
